package cn.bouncyslime.algorithms.polynomial;

/**
 * 一元多项式的相关操作，包括根据数组建立一元多项式，两个一元多项式相加，打印输出两个一元多项式
 * 作者：张一卓
 * 日期：2020/10/1
 */
public class Polynomial {
    public static void main(String[] args) {
        Item polynomial = createPolynomial(new double[]{1, 3.2, 4}, new int[]{1, 2, 5});
        Item polynomial2 = createPolynomial(new double[]{1, 5.4, 8, 3}, new int[]{1, 3, 5, 9});
        printPolynomial(polynomial);
        printPolynomial(polynomial2);
        Item addResult = addPolynomial(polynomial, polynomial2);
        printPolynomial(addResult);
    }

    /**
     * 根据数组建立一元多项式
     * @param coefficientArray 系数数组
     * @param exponentArray 指数数组
     * @return 一元多项式的头结点
     */
    public static Item createPolynomial(double[] coefficientArray, int[] exponentArray){
        int length = coefficientArray.length;
        Item polynomial = new Item();
        polynomial.setCoefficient(0);
        polynomial.setExponent(-1);
        Item temp = polynomial;
        for (int i=0; i<length; i++){
            temp.setNext(new Item());
            temp = temp.getNext();
            temp.setCoefficient(coefficientArray[i]);
            temp.setExponent(exponentArray[i]);
        }
        return polynomial;
    }

    /**
     * “和多项式”链表中的结点无需另外生成，而应从两个多项式的链表中摘取。
     * 其运算规则如下：
     * 假设指针qa和qb分别指向多项式A和多项式B中当前进行比较的某个结点，则比较两个节点中的指数项，有如下情况：
     * - 指针qa所指结点的指数值 < 指针qb所指结点的指数值，则应摘取qa指针所指结点插入到“和多项式”链表中去
     * - 指针qa所指结点的指数值 > 指针qb所指结点的指数值，则应摘取qb指针所指结点插入到“和多项式”链表中去
     * - 指针qa所指结点的指数值 = 指针qb所指结点的指数值，则将两个结点中的系数相加，若和不为零，则修改qa所指结点的系数值，同时释放qb所指结点；反之，从多项式A的链表中删除相应结点，并释放指针qa和qb所指结点。
     * @param polynomial 多项式 头结点
     * @param polynomial2 多项式 头结点
     * @return 相加之后的多项式
     */
    public static Item addPolynomial(Item polynomial, Item polynomial2){
        Item result = polynomial, temp = polynomial;
        polynomial = polynomial.getNext();
        polynomial2 = polynomial2.getNext();
        while (polynomial != null && polynomial2 != null){
            if (polynomial.getExponent() < polynomial2.getExponent()){
                temp.setNext(polynomial);
                temp = temp.getNext();
                polynomial = polynomial.getNext();
            }else if(polynomial.getExponent() > polynomial2.getExponent()){
                temp.setNext(polynomial2);
                temp = temp.getNext();
                polynomial2 = polynomial2.getNext();
            }else {
                double addCoefficient = polynomial.getCoefficient() + polynomial2.getCoefficient();
                if (addCoefficient != 0){
                    polynomial.setCoefficient(addCoefficient);
                    temp.setNext(polynomial);
                    temp = temp.getNext();
                }
                polynomial = polynomial.getNext();
                polynomial2 = polynomial2.getNext();
            }
        }
        temp.setNext(polynomial != null ? polynomial : polynomial2);
        return result;
    }

    public static void printPolynomial(Item item){
        System.out.println("===> 输出一元多项式，用x表示“元”");
        item = item.getNext();
        while (item != null){
            System.out.print(item.getCoefficient() + "*x^" + item.getExponent());
            if (item.getNext() != null)
                System.out.print(" + ");
            item = item.getNext();
        }
        System.out.println();
    }
}
